package arithmetic1.test;


/*
    一个机器人只能向下和向右移动，每次只能移动一步，设计一个算法求从(0,0)移动到(m,n)有多少条路径。
 */
public class Work1 {
    public static void main(String[] args) {
        int sum = pathCount(2, 2);
        System.out.println("路径总数:"+sum);
    }


    //动态规划求解总路径数,m代表终点的横坐标，n代表终点的纵坐标
    public static int pathCount(int m,int n){
        //创建一个存储每个点的路径数的二维数组  行为终点纵坐标+1，列为终点横坐标+1
        int pathCount[][]=new int[n+1][m+1];
        //将数组初始化
        for(int i=0;i<pathCount.length;i++){
            for(int j=0;j<pathCount[i].length;j++){
                if(i==0 || j==0){
                    pathCount[i][j]=1;
                }
            }
        }
        pathCount[0][0]=0;
        //动态规划
        for(int i=1;i<m+1;i++){    //i遍历列
            for(int j=1;j<n+1;j++){ //j遍历行
                pathCount[j][i]=pathCount[j-1][i]+pathCount[j][i-1];
            }
        }
        //将改点的路径总和返回
        return pathCount[n][m];
    }

}
